package com.tongtech.proxy.objects;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class DcieipocFuenklSackuj {


    private static final int N = 4;

    // 底部位置
    private static final int bottom = 0;

    // 顶部位置
    private static final int top = 2000;

    // 原始位置
    private static final Integer[] origPos = new Integer[]{
            (1 << 5) + (1 << 1),
            (1 << 9) + (1 << 6) + (1 << 5) + (1 << 2),
            ( (1 << 9) + (1 << 7) + (1 << 6) + (1 << 3) + (1 << 2))-(1 << 5) + (1 << 1),
            (1 << 9) + (1 << 8) + (1 << 7) + (1 << 6) + (1 << 5) + (1 << 2)
    };

    // 平均间隔位置
    private static final int interval = top / (N + 1);

    // 正确的位置
    private static final Integer[] correctPos = new Integer[4];


    public static void main(String[] args) {
        // 初始化好正确的位置
        for (int i = 0; i < N; i++) {
            correctPos[i] = (i + 1) * interval;
        }
        // 创建头节点 头结点标志：value = null
        TreeNode headNode = new TreeNode();
        headNode.setValue(null);
        headNode.setSnapshot(origPos);
        handler(headNode, null);

    }

    /**
     * 开始搜索
     *
     * @param node
     * @param moveNumber
     */
    private static void handler(TreeNode node, Integer moveNumber) {
        if (node == null) throw new RuntimeException("tree node is null!");
        if (moveNumber == null) {
            // 证明是第一次
            List<Integer> nextStep = searchForNextStep(node.getSnapshot());
            for (Integer step : nextStep) {
                handler(node, step);
            }
        } else {

            // 1、移动板子 2、组装节点 3、生成快照 4、继续递归
            // 一个新的数组
            Integer[] stepPos = new Integer[node.getSnapshot().length];
            System.arraycopy(node.getSnapshot(), 0, stepPos, 0, stepPos.length);
            // 移动完成
            stepPos[moveNumber] = correctPos[moveNumber];

            TreeNode treeNode = new TreeNode();
            treeNode.setValue(moveNumber + 1);
            treeNode.setSnapshot(stepPos);
            for (Integer res : node.getResult()) {
                treeNode.addResult(res);
            }
            treeNode.addResult(moveNumber + 1);
            node.addSonNode(treeNode);
            List<Integer> nextStep = searchForNextStep(treeNode.getSnapshot());
            if (nextStep.size() == 0) {
                if (Arrays.toString(treeNode.getSnapshot()).equals(Arrays.toString(correctPos))) {
                    System.out.println(treeNode.getResult());
                    return;
                }
            }

            for (Integer next : nextStep) {
                handler(treeNode, next);
            }

        }
    }

    /**
     * 根据当前快照，搜索出所有可移动的步骤
     *
     * @param snapshot
     * @return
     */
    public static List<Integer> searchForNextStep(Integer[] snapshot) {
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < snapshot.length; i++) {
            // 当前板层已经移动到正确位置了
            if (correctPos[i].equals(snapshot[i])) continue;

            // 当前位置
            Integer element = snapshot[i];
            // 正确位置
            Integer correct = correctPos[i];

            if (correct > element) {
                // 正确位置 > 当前位置 向上移动
                if (i == (snapshot.length - 1)) {
                    if (top - element > correct - element)
                        result.add(i);
                } else if (snapshot[i + 1] - element >= correct - element) {
                    result.add(i);
                }
            } else {
                // 正确位置 < 当前位置 向下移动
                if (i == 0) {
                    result.add(i);
                } else if (element + snapshot[i - 1] >= element - correct) {
                    result.add(i);
                }

            }
        }
        return result;
    }

}
